//这个程序执行理论最优的图染色算法
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<cusparse.h>
#include<sys/time.h>

//这里我们需要改变图染色的粒度，以16行为一个粒度
#define GRAIN_SIZE 16

#define A_ROW_SIZE 32768

//这里显示实际点的数量，用总函数除以粒度，并且补全不足的部分这里显示实际点的数量，用总函数除以粒度，并且补全不足的部分
#define A_NODE_SIZE (A_ROW_SIZE % GRAIN_SIZE ? (A_ROW_SIZE / GRAIN_SIZE + 1) : (A_ROW_SIZE / GRAIN_SIZE))

//这个数组记录每一个还没有染色的节点的编号
__global__ void init_need_to_color_device(int* need_to_color_device, int size){
    //每个线程为一个位置附上一个数字
    int thread_id = threadIdx.x + blockIdx.x * blockDim.x;

    //附上一个数字
    if(thread_id < A_NODE_SIZE){
        need_to_color_device[thread_id] = thread_id;
    }
}

//用一个函数来得到染色的最大节点
//如果对应颜色编号有颜色，那么我们就将color_arr的对应为置为1如果对应颜色编号有颜色，那么我们就将color_arr的对应为置为1
__global__ void get_color_count(int* coloring, int row_num, int* color_arr){
    //计算当前节点的线程号
    int thread_id = threadIdx.x + blockIdx.x * blockDim.x;

    int color = coloring[thread_id];

    //如果颜色没有登记，那么我们就登记颜色
    if(color_arr[color] == 0){
        color_arr[color] = 1;
    }
}

//这里执行不进行bit压缩的方案，进行染色工作
//我们将row_num重命名为node_num
__global__ void AssignColors_no_compress(int* A_device, size_t pitch,int* element_num_each_row_device, 
int node_num, int* need_color_num, int* coloring, int *need_to_color){
    //计算当前线程号，每个线程负责一个节点
    int thread_id = threadIdx.x + blockIdx.x * blockDim.x;

    //排除掉不存在的点
    if(thread_id < *need_color_num){
        //获取当前节点的编号
        int target_point = need_to_color[thread_id];

        //当前节点的邻居节点的相邻行的数量
        //因为16行为一组，所以，邻居节点的数量也要计算16行的
        int i;
        
        //准确说不是邻居节点，而且邻居行的数量，现在这个图结构有点和行两个层次
        //我们需要得到的是点之间的相邻问题，但是我们需要用行来判断这种相邻问题。
        int neighbor_row_num = 0;

        //申请一个数组来存储周围节点的情况
        int can_not[27 * GRAIN_SIZE];

        //初始化这个数组
        for(i = 0; i < 27 * GRAIN_SIZE; i++){
            can_not[i] = 0;
        }

        //邻居行所对应的邻居节点的颜色的临时变量
        int neighbor_point_color;

        //邻居行的编号
        int neighbor_row;

        //邻居点的编号
        int neighbor_point;

        //用两层循环来遍历所有的邻居行，第一层遍历每一行，第二层遍历每一行中的每一个元素
        int j;

        //邻接矩阵的指针
        int* A_device_row;

        for(i = target_point * GRAIN_SIZE; i < (target_point + 1) * GRAIN_SIZE; i++){
            //遍历所有行
            //获取每一行节点的数量
            neighbor_row_num = element_num_each_row_device[i];

            //获取某一行的指针
            A_device_row = (int*)((char*)A_device + i * pitch); 

            //遍历每一行
            for(j = 0; j < neighbor_row_num; j++){
                
                //获取邻居点的编号
                neighbor_point = A_device_row[j] / GRAIN_SIZE;

                //获取邻居节点的颜色
                neighbor_point_color = coloring[neighbor_point];

                //如果邻居节点已经染色，那么我们就更新当前节点不能染的颜色
                if(neighbor_point_color != 0){
                    //已经染色
                    can_not[neighbor_point_color] = 1;
                }
            }
        }

        //这里已经记录了周围节点的所有颜色，然后再进行移位计算，找出可以染色的最小颜色编号
        //下面这个数字存储了当前节点需要染的颜色，一开始默认是1
        int target_point_color = 1;

        while(can_not[target_point_color] == 1){
            target_point_color++;

            if(target_point_color > 63){
                printf("出错了，不用那么多颜色\n");
            }
        }
        
        //当前节点的颜色已经拿到了
        coloring[target_point] = target_point_color;
        
        //对于已染色节点的数量，在检测冲突的时候更新
    }
}

//这里执行纠错工作
//传入的参数几乎没有区别，主要就是更新need_color_num和need_to_color两个变量，已经将一部分coloring的点取消掉
//我们需要在这个函数中更新颜色数量
__global__ void JudgeConflict(int* A_device, size_t pitch,int* element_num_each_row_device, 
int node_num, int* need_color_num, int* coloring, int *need_to_color, int *need_to_color_new,
int* need_color_num_new, int* already_color_num){
    //用一个线程扫描所有的节点，然后更新need_to_color
    //计算当前线程号，每个线程负责上次受到染色的节点，然后得出一个新的需要染色节点的列表
    //我们只需要计算当前节点是不是需要进行下一轮染色就可以了
    int thread_id = threadIdx.x + blockIdx.x * blockDim.x;

    if(thread_id < *need_color_num){
        //获取当前节点的编号
        int target_point = need_to_color[thread_id];

        //当前节点的邻居节点中每一行元素的数量
        int neighbor_row_num = 
    }
}